Maratones competidas/Maratón Nacional 2011/workspace/c/c7.cpp

   1 // Equipo Poncho, Carriel y Ruana
   2 using namespace std;
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <iterator>
   6 #include <sstream>
   7 #include <fstream>
   8 #include <cassert>
   9 #include <climits>
  10 #include <cstdlib>
  11 #include <cstring>
  12 #include <string>
  13 #include <cstdio>
  14 #include <vector>
  15 #include <cmath>
  16 #include <queue>
  17 #include <stack>
  18 #include <list>
  19 #include <map>
  20 #include <set>
  21
  22 template <class T> string toStr(const T &x)
  23 { stringstream s; s << x; return s.str(); }
  24 template <class T> int toInt(const T &x)
  25 { stringstream s; s << x; int r; s >> r; return r; }
  26
  27 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  28 #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
  29 #define D(x) cout << #x " = " << (x) << endl;
  30
  31 const double EPS = 1e-9;
  32
  33 int cmp(double x, double y = 0, double tol = EPS) {
  34     return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
  35 }
  36
  37 #define INPUT_FILE "compression"
  38
  39 const int MAXBASES = 105, oo = 1 << 28;
  40 int bases[MAXBASES];
  41
  42 int B, D;
  43 int bit[20]; // bit[i] = index of term i in the document
  44
  45 int dp[MAXBASES][1 << 16];
  46
  47 int docSize;
  48
  49 void binary(int x){
  50     for (int i = 0; i < 16; ++i){
  51         printf("%d", !!(x & (1 << i)));
  52     }
  53 }
  54
  55 int v[16];
  56
  57 bool canDelete(int base) {
  58     for (int j = 0; j < 16; ++j) {
  59         if (base & (1 << j)){
  60             if (v[j] <= 1) return false;
  61         }
  62     }
  63     return true;
  64 }
  65
  66 bool noSolution(int doc) {
  67     for (int j = 0; j < 16; ++j) {
  68         if (doc & (1 << j)) {
  69             if (v[j] == 0) return true;
  70         }
  71     }
  72     return false;
  73 }
  74
  75 void solve(int doc) {
  76     for (int i = 0; i < 16; ++i) {
  77         v[i] = 0;
  78     }
  79     int ans = 0;
  80     for (int i = 0; i < B; ++i) {
  81         if ((bases[i] | doc) == doc){
  82             //printf("took base i = %d\n", i);
  83             for (int j = 0; j < 16; ++j){
  84                 if (bases[i] & (1 << j)) {
  85                     v[j]++;
  86                 }
  87             }
  88             ans++;
  89         }
  90     }
  91     for (int i = 0; i < B; ++i) {
  92         if (canDelete(bases[i])) {
  93             ans--;
  94             //printf("removed base i = %d\n", i);
  95             for (int j = 0; j < 16; ++j) {
  96                 if (bases[i] & (1 << j)) {
  97                     v[j]--;
  98                 }
  99             }
 100         }
 101     }
 102
 103     if (noSolution(doc)) {
 104         printf("0");
 105         return;
 106     }
 107     printf("%d", ans);
 108
 109 }
 110
 111 bool popcount(int a, int b) {
 112     return __builtin_popcount(a) < __builtin_popcount(b);
 113 }
 114
 115 int main(){
 116     freopen(INPUT_FILE ".in", "r", stdin);
 117     while (cin >> B >> D) {
 118         if (B == 0 and D == 0) break;
 119         for (int i = 0; i < B; ++i) {
 120             bases[i] = 0;
 121
 122             int k; cin >> k;
 123             while (k--) {
 124                 int x; cin >> x; x--;
 125                 bases[i] |= (1 << x);
 126             }
 127             //printf("base[i=%d] = %d\n", i, bases[i]);
 128         }
 129         sort(bases, bases + B, popcount);
 130         for (int j = 0; j < D; ++j) {
 131             int doc = 0;
 132             cin >> docSize;
 133             int k = docSize;
 134             while (k--) {
 135                 int x; cin >> x; x--;
 136                 doc |= (1 << x);
 137             }
 138             //printf("doc = %d\n", doc);
 139             solve(doc);
 140             if (j + 1 < D) printf(" ");
 141         }
 142         puts("");
 143
 144     }
 145     return 0;
 146
 147 }